package leetcode_top;

import org.junit.Test;

public class Ex41 {
    class Solution {
        public int firstMissingPositive(int[] nums) {
            //将正数 n放到n的位置（若n大于len或者n<=0,忽略）
            //再进行一遍遍历，找到第一个不符合该定义的位置
            if (nums == null) return 1;
            int len = nums.length;
            // if (len == 1) return nums[0] == 1 ? 2 : 1;
            for (int i = 0; i < len; i++) {
                if (nums[i] > 0 && nums[i] <=len && nums[nums[i] - 1] != nums[i]) {
                    swap(nums, i, nums[i]  - 1);
                }
            }

            for (int i = 1; i <= len; i++) {
                if (nums[i - 1] != i) {
                    return i;
                }
            }
            return len + 1;
        }

        private void swap(int[] nums, int index1, int index2) {
            int temp = nums[index1];
            nums[index1] = nums[index2];
            nums[index2] = temp;
        }
    }

    @Test
    public void test() {
        Solution s = new Solution();
        int[] nums = {-3,9,16,4,5,16,-4,9,26,2,1,19,-1,25,7,22,2,-7,14,2,5,-6,1,17,3,24,-4,17,15};
        System.out.println(s.firstMissingPositive(nums));
    }

    public class Solution1 {

        public int firstMissingPositive(int[] nums) {
            int len = nums.length;
    
            for (int i = 0; i < len; i++) {
                while (nums[i] > 0 && nums[i] <= len && nums[nums[i] - 1] != nums[i]) {
                    // 满足在指定范围内、并且没有放在正确的位置上，才交换
                    // 例如：数值 3 应该放在索引 2 的位置上
                    swap(nums, nums[i] - 1, i);
                }
            }
    
            // [1, -1, 3, 4]
            for (int i = 0; i < len; i++) {
                if (nums[i] != i + 1) {
                    return i + 1;
                }
            }
            // 都正确则返回数组长度 + 1
            return len + 1;
        }
    
        private void swap(int[] nums, int index1, int index2) {
            int temp = nums[index1];
            nums[index1] = nums[index2];
            nums[index2] = temp;
        }

    }
}
